package mathMethod;

import java.util.Random;

public class RandomPick {

    /**
     * LeetCode T528 按权重随机选择
     * 总结：使用前缀和进行求解
     * @param args
     */
    public static void main(String[] args) {

    }
}

class Solution2 {

    private int[] arr;
    private int[] prefixSum;

    private Random random = new Random();


    public Solution2(int[] w) {
        this.arr = w;
        initPrefixSum();
    }
    //初始化前缀和
    private void initPrefixSum(){
        if (arr == null){
            return;
        }
        this.prefixSum = new int[arr.length];
        prefixSum[0] = arr[0];
        for (int i = 1; i < arr.length; i++){
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        }
    }

    //根据要求生成随机下标
    private int getIndex(){
        int left = 0, right = arr.length - 1, mid;
        int num = random.nextInt(prefixSum[prefixSum.length - 1]) + 1;
        while (left <= right){
            mid = (left + right) >> 1;
            if (prefixSum[mid] == num){
                return mid;
            } else if (prefixSum[mid] > num){
                right = mid - 1;
            } else {
                left = mid + 1;
            }

        }
        return left;
    }
    public int pickIndex() {
        return getIndex();
    }
}
